1. Field of the Invention
The present invention relates to a solution apparatus useful for solving the problem of how to properly assign plural elements to plural cells.
2. Description of the Background
An apparatus which effectively solves the combinatorial optimization problem is important in LSI design to determine element placement. For example, combinatorial optimization problem is that m elements are properly assigned to n cells. Recently, a solution for the combinatorial optimization problem by using a neural network has been proposed. The method which Hopfield proposed is representative. This method is disclosed in the following document.
"Hopfield and Tank; PA1 "Biological Cybernetics, vol. 52" PA1 PP 141-152, 1985"
LSI element placement by way of Hopfield's method is explained as follows. The placement problem for plural elements being placed on a circuit map is that each element is to be placed on a single one of a plurality of cells in such a way as to minimize the virtual path length between elements. In this case,
dij: distance between cell i and cell j PA0 Rxy: path between element x and element y PA0 CAPi: the number of elements being placed on cell i PA0 Vxi: output of neuron PA0 [VXi=1] element x is placed on cell i PA0 Vxi=0] element x is not placed on cell i
The energy function E of a neural network for solving the LSI element placement problem is as follows. ##EQU1## The first term of the right side of the equation is the constraint for each neuron to generate "1" or "0" as the output Vxi. The second term of the right side of the equation is the constraint for each element to be placed on one cell respectively. The third term of the right side of the equation represents the capacity for each cell to contact multiple elements. And the fourth term of the right side of the equation is the evaluation function used to minimize the virtual path length between elements. By solving the energy function, the optimum solution for LSI element placement problem is obtained.
FIG. 1A shows plural elements, A-H, being drawn on the circuit chart and plural cells, 1-8, being arranged, for example, on the substrate. FIG. 1B shows a neural network according to the elements and cells as shown in FIG. 1A. In FIG. 1B, sixty four squares, (A,1)-(H,8), represent neurons and the white/black circle on the neuron represents the weight of connection. The white circle is a positive weight of connection and the black circle is a negative weight of connection. In short, because the number of elements is eight (A-H), and the number of cells is eight (1-8), the number of neuron is sixty-four (=8.times.8). In FIG. 1B, the eight labels (A-H) in the horizontal row correspond to eight elements and the eight labels (1-8 in the vertical column correspond to eight cells, respectively.
In setting the weights of connection for the sixty four neurons, first the negative weights of connection are set between neurons, arranged in the vertical column. These negative weights of connection correspond to the second term of the right side of the equation for the above-mentioned energy function, and are represented by a black circle in the vertical column. In FIG. 1B, only black circles which come from the neuron (A, 1), are drawn, although in reality such black circles are also on the outer neurons.
Secondly, the negative weights of connection are set between neurons arranged in the horizontal row. These negative weights of connection correspond to the third term of the right side of the equation for the above-mentioned energy function, and are represented by a black circle in the horizontal row. In FIG. 1B, only the black circles which come from the neuron (A, 1 are drawn.)
Thirdly, positive weights of connection are set between neurons in accordance with connection status of elements, as shown in FIG. 1A. For example, element A is connected with element B and element C. Therefore, a positive weight of connection is set between element A and element B, element A and element C. (In FIG. 1B, white circles from neuron (A, 1) only are drawn.) If element A is placed at cell 1 and element B is placed at cell 2, or cell 3, or cell 4, the positive weight of connection between element A and element B is strong because its distance is short. On the other hand, if element B is placed at cell 5, or cell 6, or cell 7, or cell 8, the positive weight of connection between element A and element B is weak because its distance is long. Therefore, the values of the white circles between neuron (A, 1), and neuron (B, 2) (B, 3) (B, 4) (C, 2) (C, 3) (C, 4) are high. The values of the white circles between neuron (A, 1) and neuron (B, 5) (B, 6) (B, 7) (B, 8) (C, 5) (C, 6) (C, 7) (C, 8) are low. These positive weights of connection correspond to the fourth term of the right side of the equation for the above-mentioned energy function.
Lastly, external input "1" is assigned for neuron (A, 1), because element A is desired to be fixed at cell 1 according to a design constraint. It is represented as an arrow in FIG. 1B. Then, from the external input "1" as the beginning, the signal is transmitted between neutrons in order. And when the neural network enters a stable state (the output of each neuron is unchangeable), the output of each neuron corresponds to an answer for the LSI element placement problem. FIG. 1C shows the output when the neurons are in a stable state. The neuron number which generates signal "1", corresponds to the answer, which a representation of the combination of the element and the cell where it is to be placed.
However, the above-mentioned method is defective for packaging purposes because the number of neurons equals the product of the number of elements and the number of cells. And the number of weights of connection equals a square of the number of neurons. In short, it is necessary for the neural network to equip a great many neurons and weights of connections. Therefore, packaging the neural network is not practical because of cost.